package com.hyper_yang.algorithmRecord.dynamicProgramming;

public class Fibonacci {
    // 方法一: 利用数学递推式，直接递归
    public int fibonacci1(int n) {
        // 基准情况
        if (n == 0) return 0;
        if (n == 1) return 1;
        // 递归调用
        return fibonacci1(n-2) + fibonacci1(n-1);
    }

    // 方法二: 动态规划
    public int fibonacci2(int n) {
        // 返回基准情况:
        if (n == 1 || n == 2) return 1;
        // 定义一个状态数组，保存 fibonacci(n)的计算结果
        int[] dp = new int[n];
        dp[0] = dp[1] = 1; // 边界条件 fibonacci(1)、fibonacci(2)
        // 状态转移方程 递推
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i-2] + dp[i-1];
        }
        return dp[n-1];
    }

    // 可以只保存前两个数，做一个空间优化。
    public int fibonacci(int n) {
        // 返回基准情况
        if (n == 1 || n == 2) return 1;
        // 定义记忆化方式 (状态变量)
        int pre2 = 1, pre1 = 1; // 定义边界条件
        int current = 0;
        // 定义状态转移方程
        for (int i = 2; i < n; i++) {
            current = pre2 + pre1;
            pre2 = pre1;
            pre1 = current;
        }
        return current;
    }
    public static void main(String[] args){
        Fibonacci fib = new Fibonacci();
        System.out.println(fib.fibonacci(9));
    }
}
